Electronic systems and circuits have made a significant contribution towards the advancement of modern society and are utilized in a number of applications to achieve advantageous results. Numerous electronic technologies such as digital computers, calculators, audio devices, video equipment, and telephone systems facilitate increased productivity in analyzing and communicating data, ideas and trends in most areas of business, science, education and entertainment. Often these advantageous results are achieved through the use of distributed resources that communicate with each other over a network and it is usually desirable for the information to be communicated rapidly. However, it is often difficult to maximize utilization of available resources to achieve fast and efficient communication of information.
The rate at which information is communicated over a network is typically referred to as bandwidth. Tremendous growth in communication traffic due to a seemingly insatiable desire for new services has led to greater demand for increased bandwidth capabilities and is driving the rapid deployment of advanced communication networks. Traditional communication networks can include a variety of architectures utilizing numerous communication protocols such as Fiber Distributed Data Interface (FDDI), Dynamic Packet Transport (DPT), Packet Over Sonet (POS), Asynchronous Transfer Mode (ATM), Ethernet, token ring, Transmission Control Protocol/Internet Protocol (TCP/IP), plain old telephone system (POTS), Cable, Digital Subscriber Line (DSL), etc. The communication networks typically include switches coupled together by multiple communication links.
One traditional approach to communicating information via a network includes “cell switching” in which digital information is segmented into units called “cells” or packets that are transmitted from a source node to a destination node through a “connection” in a digital network. A communication link can communicate or carry a variety of different connections simultaneously. Accordingly, cells belonging to each connection are often handled or serviced differently at each switch in order to meet overall network goals.
Many traditional switches include a memory or buffer used for temporarily holding or storing information prior to transmission on a communication link. The memory is often arranged in logical queues which are used to separate information based upon different types of services and/or connections. For example, higher priority information (e.g., information required to be transmitted in real time) is associated with higher priority connections and stored in queues that have a higher priority of service. In some cases, a separate queue may be assigned to each connection. “Servicing” of a queue is usually accomplished by sending information (e.g., a packet) from that queue out “into” the network on a communication link. For example, the information packet is removed from its associated queue in the memory or buffer and forwarded on the network towards its final destination.
The information is usually forwarded in accordance with a scheme that determines when the information is sent. In advanced modern communication system nodes (e.g., switches) it is often desirable to support and take advantage of characteristics associated with multiple scheduling schemes. One traditional scheduling scheme is a rate based scheduling scheme which usually involves precise rate control. Another conventional scheduling scheme is a non-rate base scheduling scheme. Regardless of the scheduling scheme, it is usually important for information to be granted appropriate access to bandwidth on each link or port. For example, it is usually desirable for scheduling schemes to grant greater link access to high priority information while still ensuring that other information also obtains appropriate access to the link and is not shut out. Non-rate based scheduling schemes, such as round robin (RR) or weighted round robin (WRR), are usually relatively simple and typically work well for ports or communication links.
In addition to planning information communication between ports or links efficiently and fairly, it is usually desirable to distribute bandwidth efficiently and fairly between queues accessing a port when the port is active. Traditional approaches usually utilize a calendar based (e.g., “slotted wheel”) approach for scheduling rate based flows associated with a queue. However, traditional calendar schemes often encounter difficulty in scheduling queues with varying rate connection flows. Traditional attempts at efficiently scheduling queues with varying rate connection flows are typically very complicated and cycle intensive. In addition, utilizing a calendar scheme to schedule queue connection flows involving different packet sizes on a link or port usually introduces difficulties in maximizing utilization of available bandwidth of the link.